#include <bits/stdc++.h>
#include "utils.h"

using namespace std;


void backtrack(vector<int> &state, const vector<int> &choices, 
            vector<bool> &selected, vector<vector<int>> &res)
{
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }

    // 
    for (int i = 0; i < choices.size(); i++) {
        bool choice = selected[i];
        if (choice == false) {
            selected[i] = true;
            state.push_back(choices[i]);
            backtrack(state, choices, selected, res);

            selected[i] = false;   // huisuo
            state.pop_back();      // huisuo vs dfs
        }
    }
}


void permutation(std::vector<int>& arr) {
    std::vector<int>              state;   // path
    std::vector<std::vector<int>> res;     // result  120 * 5
    std::vector<bool> selected(arr.size(), false); 

    backtrack(state, arr, selected, res);

    // result  120 * 5
    for (int i = 0; i < res.size(); i++)
    {
        printf("line %3d: ", i);
        for (int j = 0; j < arr.size(); j++)
        {
            printf("%d ", res[i][j]);
        }
       printf("\n");
    }
    
    return;
}


int main() {
    // std::vector<int> arr = {1,2,3,4,5 /*,6,7,8,9,10*/ };
    Vec<int> arr = {1,2,3,4,5 /*,6,7,8,9,10*/ };
    permutation(arr);

    return 0;
}